for i in range(0,int(input())):
count=0
n,k=map(int,input().split())
if(n<k or k==1):
print(n)
else:
while(n>0):
r=n%k
if(r>0):
n=n-r
count+=r
else:
n=n//k
count+=1
print(count)#include <iostream>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
long long int n, k;
cin >> n >> k;
long long int h = 0;
while (n > 0)
{
if (n % k != 0)
{
h += (n % k);
n = n - (n%k);
}
else
{
n = n / k;
h++;
}
}
cout << h << endl;
}
}141A - Amusing Joke | 112A - Petya and Strings |
677A - Vanya and Fence | 1621A - Stable Arrangement of Rooks |
472A - Design Tutorial Learn from Math | 1368A - C+= |
450A - Jzzhu and Children | 546A - Soldier and Bananas |
32B - Borze | 1651B - Prove Him Wrong |
381A - Sereja and Dima | 41A - Translation |
1559A - Mocha and Math | 832A - Sasha and Sticks |
292B - Network Topology | 1339A - Filling Diamonds |
910A - The Way to Home | 617A - Elephant |
48A - Rock-paper-scissors | 294A - Shaass and Oskols |
1213A - Chips Moving | 490A - Team Olympiad |
233A - Perfect Permutation | 1360A - Minimal Square |
467A - George and Accommodation | 893C - Rumor |
227B - Effective Approach | 1534B - Histogram Ugliness |
1611B - Team Composition Programmers and Mathematicians | 110A - Nearly Lucky Number |